package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by baoyunfeng on 2018/1/31.
 * https://leetcode.com/problems/two-sum/description/
 *
 * 1. 一种思路从首尾搜索两个数的和，并逐步逼近。
 2. 另外一种思路是固定一个数A，看SUM-A是否在这个数组之中。
 */
public class Two_Sum {

    public static void main(String args[]){
        int nums[] = {3,2,4};
        for(int i = 0 ;i <nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        System.out.println(" ");
        int result[] = twoSum(nums,6);
        for(int i = 0 ;i <result.length;i++){
            System.out.print(result[i]+" ");
        }
    }

    public static int[] twoSum(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;

        int[] index = new int[nums.length];
        for(int i = 0;i<nums.length ;i++){
            index[i] = i;
        }

        for (int i = 0 ;i <nums.length;i++){
            for(int j = 0 ; j< nums.length-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;

                    int flag = index[j];
                    index[j] = index[j+1];
                    index[j+1] = flag;
                }
            }
        }

        while(start<end){
            if(nums[start]+nums[end]>target){
                end--;
            }else if(nums[start]+nums[end]<target){
                start++;
            }else{
              break;
            }
        }

        return new int[]{index[start],index[end]};
    }

    public static void sort(int nums[]){
        for (int i = 0 ;i <nums.length;i++){
            for(int j = 0 ; j< nums.length-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

    public int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
